package Hot100.Medium.String_2Pointer.String;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class LC438_FindAnagramsInString {
    public static void main(String[] args) {
        String s = "cbaebabacd";
        String p = "abc";
        LC438_FindAnagramsInString solution = new LC438_FindAnagramsInString();
        System.out.println(solution.findAnagrams(s, p));
    }
    public List<Integer> findAnagrams(String s, String p){
        int len = p.length();
        int left = 0;
        int right = left + len;
        List<Integer> res = new ArrayList<>();
        while(right <= s.length()){
            String cur = s.substring(left, right);
            if(isAnagrams(cur, p)){
                res.add(left);
            }
            left++;
            right++;
        }
        return res;
    }

    boolean isAnagrams(String cur, String p){
        if (cur.length() != p.length()) {
            return false;
        }
        int[] count = new int[26]; // 统计字母频率
        // 统计 cur 中每个字符
        for (char c : cur.toCharArray()) {
            count[c - 'a']++;
        }
        // 抵消 p 中的字符
        for (char c : p.toCharArray()) {
            count[c - 'a']--;
        }
        // 检查是否所有计数为 0
        for (int num : count) {
            if (num != 0) {
                return false;
            }
        }
        return true;
    }
}
